package leetcode.code0519;

import java.util.HashMap;
import java.util.Map;

import leetcode.helper.HelpDebug;

/**
 * 超出内存限制
 *
 * @author CaoYu
 * @date 2021年11月27日
 * @description
 */
public class Solution {

//	private Integer[] datas;
	private int range;
	private int size;
	private int n;
	private int last;
	private Map<Integer, Integer> datas;

	public Solution(int m, int n) {
		this.n = n;
		this.size = m * n;// 原始数组规模
		this.range = size;// 随机数范围
		this.last = size - 1;// 最后一个数下标
//		this.datas = new Integer[size];
		this.datas = new HashMap<>();
	}

	public int[] flip() {
		int num = this.random();
//		Integer data = datas[num];
		Integer data = datas.get(num);
		Integer lastData = datas.get(this.last);
		if (data == null) {// 没数字，随机脚标
			int temp = lastData == null ? this.last : lastData;// 将最后一个数或者脚标放置到这一位上
			datas.put(num, temp);
			this.last--;// 缩减范围
			return this.num2array(num);// 脚标num是未到达的点
		} else {
			int temp = lastData == null ? this.last : lastData;// 将最后一个数或者脚标放置到这一位上
			datas.put(num, temp);
			this.last--;
			return this.num2array(data);// data是未到达的点，缩减范围时候换过来的
		}
	}

	public void reset() {
		this.range = size;
		this.last = size - 1;
//		this.datas = new Integer[size];
		this.datas = new HashMap<>();
	}

	private int random() {
		return (int) (Math.random() * range--);
	}

	private int[] num2array(int num) {
		return new int[] { num / n, num % n };
	}

	public static void main(String[] args) {
		Solution solution = new Solution(3, 1);
		int ans[] = null;
		ans = solution.flip(); // 返回 [1, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同
		HelpDebug.print(ans);
		ans = solution.flip(); // 返回 [2, 0]，因为 [1,0] 已经返回过了，此时返回 [2,0] 和 [0,0] 的概率应当相同
		HelpDebug.print(ans);
		ans = solution.flip(); // 返回 [0, 0]，根据前面已经返回过的下标，此时只能返回 [0,0]
		HelpDebug.print(ans);
//		solution.reset(); // 所有值都重置为 0 ，并可以再次选择下标返回
//		ans = solution.flip(); // 返回 [2, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同
//		H.printObject(ans);
	}

}
